package com.zjsru.oneDay202212;

/**
 * @Author: CookLee
 * @Date: 2022/12/4
 * 最接近目标价格的甜点成本:
 * 必须选择 一种 冰激凌基料。
 * 可以添加 一种或多种 配料，也可以不添加任何配料。
 * 每种类型的配料 最多两份 。
 * baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
 * toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
 * target ，一个整数，表示你制作甜点的目标价格。
 *
 * 输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10
 * 输出：10
 * 解释：考虑下面的方案组合（所有下标均从 0 开始）：
 * - 选择 1 号基料：成本 7
 * - 选择 1 份 0 号配料：成本 1 x 3 = 3
 * - 选择 0 份 1 号配料：成本 0 x 4 = 0
 * 总成本：7 + 3 + 0 = 10 。
 *
 * 输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
 * 输出：17
 * 解释：考虑下面的方案组合（所有下标均从 0 开始）：
 * - 选择 1 号基料：成本 3
 * - 选择 1 份 0 号配料：成本 1 x 4 = 4
 * - 选择 2 份 1 号配料：成本 2 x 5 = 10
 * - 选择 0 份 2 号配料：成本 0 x 100 = 0
 * 总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。
 *
 * 输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9
 * 输出：8
 * 解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。
 */
public class ClosestCost {
    
    int ans = 0x3f3f3f3f;
    
    /**
     * 按照每一种配料去搜索，每种配料有三种选择：[选1个，选2个，不选]，保存最优的结果即可
     */
    public int closestCost(int[] baseCosts, int[] toppingCosts, int target) {
        for (int num : baseCosts) {
            dfs(0, num, toppingCosts, target);
        }
        return ans;
    }
    /**
     * @param i 选择的配料顺序
     * @param sum 总和值
     * @param target 目标值
     * @param toppingCosts 配料数组
     * */
    private void dfs(int i, int sum, int[] toppingCosts, int target) {
        //a 表示当前剩余缺少的数， b表示总缺少数
        int a = Math.abs(target - sum), b = Math.abs(target - ans);
        int len = toppingCosts.length;
        if (a < b) {
            ans = sum;
        }
        if (a == b && sum < ans) {
            ans = sum;
        }
        //超过要求的钱数
        if (sum > target) {
            return;
        }
        for (int j = i; j < len; j++) {
            dfs(j + 1, sum + toppingCosts[j], toppingCosts, target);
            dfs(j + 1, sum + 2 * toppingCosts[j], toppingCosts, target);
        }
    }
    
    public static void main(String[] args) {
        ClosestCost closestCost = new ClosestCost();
        int[] baseCosts = new int[] {1, 7};
        int[] toppingCosts = new int[] {3, 4};
        int target = 18;
        System.out.println(closestCost.closestCost(baseCosts, toppingCosts, target));
    }
}
